In the field of data networking, a network router typically maintains a set of queues, one per interface. Each queue holds packets scheduled to be transmitted over the respective interface. Historically, such queues used a drop-tail techniques whereby a packet is put onto the queue if the queue is shorter than its maximum size (measured in packets or in bytes), and otherwise dropped.
However, such drop-tail queuing approaches have a tendency to penalise bursty traffic flows, and to cause global synchronisation between traffic flows (the occurrence of simultaneous packet loss across many traffic flows as a result of a sudden burst of traffic, resulting in each affected traffic flow backing off its send rate at the same time, causing link utilization to drop significantly).
Active queue management (AQM) is the arbitrary reordering or dropping of network packets inside the transmit buffer of a network interface controller. By dropping packets probabilistically, AQM techniques have less of a tendency to penalise bursty flows and are typically able to avoid the problem of global synchronisation. AQM techniques drop or mark packets before the queue is full. Typically, they operate by maintaining one or more drop/mark probabilities, and probabilistically dropping or marking packets even when the queue is short. Such dropping/marking of packets provides endpoints with congestion indications before the queue is full. In this manner, AQM techniques are able to maintain shorter queue lengths than the conventional drop-tail techniques, helping to combat ‘buffer-bloat’ and reducing network latency.
Random early detection (RED), also known as random early discard or random early drop, is an early form of AQM. An objective of RED is to maintain an average queue size below a minimum threshold. In this manner, spare queue capacity is maintained to cope with short bursts of traffic. If the average queue size exceeds the minimum threshold, packets are randomly ‘marked’ based on some probability algorithm and their sources notified of congestion to reduce the window for that traffic flow. Such marking and notification may comprise simply discarding/dropping of the packet, setting a bit in a packet header, or some other feedback method understood by the transport protocol. The current feedback mechanism in TCP/IP networks is for packets to simply be dropped.
The RED algorithm uses randomization in choosing which arriving packets to drop (or mark when used in conjunction with, say, Explicit Congestion Notification—ECN). In this manner, the probability of marking a packet from a particular connection is roughly proportional to that connection's share of the bandwidth through the gateway. The algorithm monitors the average queue size and drops (or marks) packets based on statistical probabilities, and in particular based on a discard probability calculated based on the average queue length.
FIG. 1 illustrates the discard probability for a conventional RED algorithm against average queue length. If the buffer is almost empty (i.e. the queue length is below a minimum threshold 110), all incoming packets are accepted. As the queue grows and the average queue length exceeds the minimum threshold 110, the probability for dropping an incoming packet grows too. When the average queue length exceeds a maximum threshold 120, the probability of dropping (or marking) a packet becomes 1 and all incoming packets are dropped (or marked). As such, the minimum threshold value and the maximum threshold value define a packet discard queue length range maxTH-minTH. The discard probability for the conventional RED algorithm illustrated in FIG. 1 may be expressed as:
                    DP        =                  {                                                    0                                                                                  for                    ⁢                                                                                  ⁢                    0                                    ≤                  Av                  ≤                                      min                    ⁢                                                                                  ⁢                    TH                                                                                                                                                                  Av                      -                                              min                        ⁢                                                                                                  ⁢                        TH                                                                                                            max                        ⁢                                                                                                  ⁢                        TH                                            -                                              min                        ⁢                                                                                                  ⁢                        TH                                                                              *                  Max                  ⁢                                                                          ⁢                  DP                                                                                                  for                    ⁢                                                                                  ⁢                    min                    ⁢                                                                                  ⁢                    TH                                    <                  Av                  ≤                                      max                    ⁢                                                                                  ⁢                    TH                                                                                                      1                                                                                  for                    ⁢                                                                                  ⁢                    for                    ⁢                                                                                  ⁢                    max                    ⁢                                                                                  ⁢                    TH                                    <                  Av                                                                                        [                  Equation          ⁢                                          ⁢          1                ]            
RED is more fair than tail drop, in the sense that it does not possess a bias against bursty traffic that uses only a small portion of the bandwidth. The more a host transmits, the more likely it is that its packets are dropped (or marked) as the probability of a host's packet being dropped is proportional to the amount of data it has in a queue. Furthermore, the early detection of congestion helps avoid TCP global synchronization.
A limitation of the conventional RED algorithm for deriving the packet discard probability value, defined in Equation 1 above, is that the packet discard rate is too aggressive when the (average) queue length exceeds the minimum threshold value minTH by only a small amount, and too lenient (i.e. not aggressive enough) when the queue length is close to the maximum threshold value maxTH.